Dijkstra's Algorithm is already known. That algorithm keeps up-to-date a set X of vertices whose shortest distance to the origin are known. At the beginning, X only contains the vertex corresponding to the origin. At each step, one adds to X one of the remaining vertices whose distance to the origin is the shortest possible. If all the arcs have labels greater than or equal to 0, it is possible to find a minimal path from the origin toward a, vertex s using only vertices already belonging to X. For example, call “shortcut” such a path. At each step of the algorithm, an array D keeping the best shortcut to reach each vertex is used. As soon as a vertex is reached, the array D contains the shortest distance between the origin and this vertex. To rebuild the shortest path which fulfills this distance, another array C of vertices is kept up to date such that C[s] is the vertex immediately preceding s in the shortest path.
U.S. Pat. No. 6,356,911 (IBM) discloses a system of computation of shortest path. An efficient system and method are presented. They allow the search of shortest paths between multiple origin and multiple destinations. The speed of the classic Dijkstra's algorithm, which is the basis of this method of computation, is improved by using some information regarding relations between a node and a set of destinations in a graph.
The information of relation is made up by the estimation function h(v) concerning a specific node v and a set T of destinations, where h(v) is the lower bound of the set of the lengths of the shortest paths stretching from the node v as far as each of the sets of destinations T. The use of the function of estimation may improve the speed of the Dijkstra's algorithm.
U.S. 2002/0107711 (Sun Microsystems) discloses a search of shortest path using tiles and a propagation of linear cost by piece. A method to find the shortest path is described. This method uses a model in linear cost by piece to guide the search through the compact graph of tiles and to make sure that a shortest path may be found by efficient computation. The propagation function from tile segment to tile segment is used to search a target location from a source location through an area and the shortest path is found by carrying out a backward march using the cost functions computed during the search. The minimal linear convolution is used to make easier the propagation of the cost function.
U.S. 2001/0032272 (NEC) discloses a method for sorting and mailing of shortest path based on the SQ (Service Quality) for a hierarchical communication network. A router manages a network topology table and a number of resources tables corresponding to these areas of the network. Answering a user request, one of the entries of the topology table and one of the resources tables are referenced, a crossable area along the destination road and some links satisfying a SQ value specified by the user are selected. A computation is fulfilled on the selected links, this computation being conformed to Dijkstra's algorithm, to find a shortest path to the destination if the referenced entry indicates that the destination is in the local area of the router. If the entry does not indicate that, then the computation is carried on until a tree of shortest path is found for the routers bordering the crossable area or until the computation is finished if no tree is found for any of the routers and a route having an optimal SQ value is determined from the tree of shortest path.
The known methods of the prior art have in the best cases a complexity in O (a log v) where a is the number of arcs of the graph and v its number of vertices. It would therefore be advantageous to remedy the drawbacks of the prior art by providing a method of computation of the shortest path in a graph with a complexity O(l log v) where l is the average path length and v its number of vertices.